<?php
/**
 * 迷宫
 * 基于不相交集类生成迷宫
 */
class Maze
{
    /**
     * @var FastDisjointSets $disjoint 不相交集类
     * @var [] $pairList 邻接元素对
     */
    public $width=0;
    public $height=0;
    public $disjoint=null;
    public $pairList=[];
    public function __construct($width,$height)
    {
        $this->generate($width,$height);
    }
    public function generate($width=null,$height=null)
    {
        $width===null ? $width=$this->width : $this->width=$width;
        $height===null ? $height=$this->height : $this->height=$height;
        $count = $this->width * $this->height;
        $disjoint = new FastDisjointSets($count);
        $pairList = [];
        while(1){
            list($coord1,$coord2,$is_horiz)=$this->rand();
            $index1=$this->coordToIndex($coord1);
            $index2=$this->coordToIndex($coord2);
            if($disjoint->find($index1) !== $disjoint->find($index2)){
                $number=$disjoint->union($index1,$index2);
                $pairList[]=[$coord1,$coord2,$is_horiz];
                if($number <= -$count){
                    break;
                }
            }
        }
        $this->disjoint=$disjoint;
        $this->pairList=$pairList;
    }
    /**
     * 随机一对相邻元素
     */
    public function rand()
    {
        //随机出两个元素的排列方向和第一个元素的坐标，第二个坐标可以直接算出
        //方向为0表示横向排列，为1表示纵向排列
        if(rand(0,1)===0){
            //两个元素横向排列
            $coord1=[rand(0,$this->width-2),rand(0,$this->height-1)];
            $coord2=[$coord1[0]+1,$coord1[1]];
            return [$coord1,$coord2,0];
        }
        else{
            //两个元素纵向排列
            $coord1=[rand(0,$this->width-1),rand(0,$this->height-2)];
            $coord2=[$coord1[0],$coord1[1]+1];
            return [$coord1,$coord2,1];
        }
    }
    /**
     * 坐标换算成序号
     */
    public function coordToIndex($coord){
        return $this->width * $coord[1] + $coord[0];
    }
    /**
     * 序号换算成坐标
     */
    public function indexToCoord($index){
        $x = $index % $this->width;
        $y = ($index - $x) / $this->width;
        return [$x,$y];
    }
    /**
     * 打印不相交集类
     */
    public function printDisjointSets()
    {
        //将不相交集类中的列表处理成二维数组
        $list=$this->disjoint->list;
        $array=[];
        for($i=0; $i<$this->height; $i++){
            $array[$i]=[];
            $offset=$i*$this->width;
            for ($j=0; $j < $this->width; $j++) { 
                $array[$i][$j]=$list[$offset+$j];
            }
        }
        foreach($array as $line){
            print_list($line);
        }
        echo "\r\n";
    }

    /**
     * 获取表示每个相邻元素之间的墙是否连通的数据
     */
    public function getWallStatusData()
    {
        $array=[];
        for($i=0; $i < $this->height; $i++){
            for ($j=0; $j < $this->width; $j++) { 
                $array[$i][$j]=[0,0];//分别表示右侧和下方是否连通，0表示不连通，1表示连通
            }
        }
        $list=$this->pairList;
        foreach($list as $pair){
            $array[$pair[0][1]][$pair[0][0]][$pair[2]]=1;//三个维度正好表示坐标和连通方向
        }
        return $array;
    }
    public function __toString()
    {
        $output=new MazeOutput();
        return $output->fetch($this);
    }
}
